제약이 있는 최적화와 라그랑주 승수
이전 절에서, 우리는 다음 함수의 최솟값을 푸는 문제를 고려했다.
여기서 $f : \mathbb{R}^D \rightarrow \mathbb{R}$ 이다.
$\quad$ 이 절에서 우리는 추가적인 제약 조건(constraints)을 가진다. 즉, $i = 1, \dots, m$ 에 대한 실숫값 함수 $g_i : \mathbb{R}^D \rightarrow \mathbb{R}$ 에 대해, 우리는 다음과 같은 제약 있는 최적화 문제를 고려한다 (그림 7.4의 예시 참조).
그림 7.4: 제약 있는 최적화의 예시. 제약 없는 문제(등고선으로 표시됨)는 오른쪽(동그라미로 표시됨)에 최솟값을 가진다. 상자 제약 조건(box constraints, $-1 \leqslant x_1 \leqslant 1$ 이고 $-1 \leqslant x_2 \leqslant 1$ )은 최적해가 상자 내에 있어야 함을 요구하며, 그 결과 별표(star)로 표시된 최적값을 낳는다.
함수 $f$ 와 $g_i$ 는 일반적으로 비볼록(non-convex)일 수 있음을 지적해 둘 만하며, 볼록한 경우는 다음 절에서 고려할 것이다.
$\quad$ 제약 있는 문제 (7.17)을 제약 없는 문제로 변환하는 명백하지만 그다지 실용적이지 않은 한 가지 방법은 지시 함수(indicator function)를 사용하는 것이다.
여기서 $\mathbf{1}(z)$ 는 무한 계단 함수(infinite step function)이다.
이것은 제약 조건이 만족되지 않으면 무한대의 페널티를 부여하며, 따라서 동일한 해를 제공할 것이다. 하지만, 이 무한 계단 함수는 최적화하기에 똑같이 어렵다(제약 조건을 만족하지 못하는 경우 그래디언트는 정의되지 않는다). 우리는 라그랑주 승수(Lagrange multipliers)를 도입함으로써 이 어려움을 극복할 수 있다. 라그랑주 승수의 아이디어는 이 계단 함수를 (_ $\lambda$ 에 대해서_)선형 함수(linear function)로 대체하는 것이다.
$\quad$ 우리는 각 부등식 제약 조건에 대응하는 라그랑주 승수 $\lambda_i \geqslant 0$ 을 도입하여 문제 (7.17)에 라그랑지안(Lagrangian)을 연관시킨다.
여기서 마지막 줄에서 우리는 모든 제약 조건 $g_i(\boldsymbol{x})$ 를 벡터 $\boldsymbol{g}(\boldsymbol{x})$ 로 결합(concatenate)하였고, 모든 라그랑주 승수를 벡터 $\boldsymbol{\lambda} \in \mathbb{R}^m$ 로 결합하였다.
라그랑주 승수 $\lambda \ge 0$ 조건은 라그랑지안 함수가 원 목적 함수의 수학적 하한(Lower bound)이 되도록 만들기 위함이다.
어떤 파라미터 $x$ 가 제약 조건을 만족하는 상태라면, 제약식의 정의에 의해 $g(x) \le 0$ 이다. 쌍대 이론이 성립하려면, 제약 조건을 만족하는 영역에서 라그랑지안 함수가 원 목적 함수보다 작거나 같아야 한다( $\mathfrak{L}(x, \lambda) \le f(x)$ ).
즉 $f(x) + \lambda g(x) \le f(x)$ 이며, 결과적으로 $\lambda g(x) \le 0$ 이 성립해야 한다. $g(x)$ 가 0 이하인 상태에서 두 항의 곱이 0 이하가 되기 위핸 조건은 오직 $\lambda \ge 0$ 이다.
람다가 ‘패널티’로써 작동하려면 $g(x)$ 가 양수일 때(제약 조건을 위반한 경우) 패널티 항 $\lambda g(x)$ 도 양수로 작용하여 손실을 키워야하기 때문에 곱해지는 계수 $\lambda$ 역시 양수여야 한다.
원 문제의 최적해와 라그랑주 승수를 도입한 문제의 최적해는 같다. 바뀐 공간에서 람다 축을 버리고 원래 x축으로 정사영된 차원을 보면 원 문제와 같다.(뭔말임)
그럼 왜 바뀐 공간에서 최적해를 구하는가? 미분때매?
라그랑주 승수 벡터 $\boldsymbol{\lambda}$ 와 제약 함수 벡터 $\boldsymbol{g}(\boldsymbol{x})$ 는 제약 조건의 개수인 $m$ 차원 공간 $\mathbb{R}^m$ 에 존재하는데, 이때 $\mathbb{R}^m$ 공간의 각 축은 위치나 방향이 아니라, 개별 제약 조건의 ‘함숫값’과 ‘패널티 단가’를 나타낸다. 두 벡터는 단위와 성질이 다르므로 두 벡터의 내적( $\boldsymbol{\lambda}^\top \boldsymbol{g}(\boldsymbol{x})$ )을 투영이나 사이각이라는 기하학적 개념으로 해석하는 것보다 대수적인 선형 결합 또는 가중합으로 생각해볼 수 있겠다.
$\quad$ 이제 라그랑주 쌍대성(Lagrangian duality)의 아이디어를 소개한다. 일반적으로 최적화에서 쌍대성이란, 한 변수 집합 $\boldsymbol{x}$ (원 변수(primal variables)라 불림)에 대한 최적화 문제를, 다른 변수 집합 $\boldsymbol{\lambda}$ (쌍대 변수(dual variables)라 불림)에 대한 또 다른 최적화 문제로 변환하는 아이디어를 말한다. 우리는 쌍대성에 대한 두 가지 다른 접근법을 소개한다: 이 절에서는 라그랑주 쌍대성을 논의하고, 7.3.3절에서는 르장드르-펜첼(Legendre-Fenchel) 쌍대성을 논의한다.
정의 7.1. (7.17)의 문제
는 원 변수 $\boldsymbol{x}$ 에 대응하는 원 문제(primal problem)로 알려져 있다. 이와 연관된 라그랑주 쌍대 문제(Lagrangian dual problem)는 다음과 같이 주어진다.
여기서 $\boldsymbol{\lambda}$ 는 쌍대 변수이며, $\mathfrak{D}(\boldsymbol{\lambda}) = \min_{\boldsymbol{x} \in \mathbb{R}^d} \mathfrak{L}(\boldsymbol{x}, \boldsymbol{\lambda})$ 이다.
주의 (Remark). 정의 7.1을 논의함에 있어, 우리는 그 자체로도 독립적인 흥미를 끄는 두 가지 개념을 사용한다 (Boyd and Vandenberghe, 2004).
$\to$ $\min_{\boldsymbol{x}}$ 는 라그랑지안 $\mathfrak{L}(\boldsymbol{x}, \boldsymbol{\lambda})$ 를 $\boldsymbol{x}$ 에 대해 미분하여 $\nabla_{\boldsymbol{x}} \mathfrak{L} = \boldsymbol{0}$ 이 되는 점에서의 람다값을 구한 후 L에 대입하여 람다에 대한 함수 D를 만든다?
$\to$ 어떤 파라미터가 제약 조건을 만족하는 모든 상황에서, $g_i(\boldsymbol{x}) \leqslant 0$ , $\lambda_i \geqslant 0$ 이므로 $\sum_{i=1}^m \lambda_i g_i(\boldsymbol{x})$ 은 항상 음수(또는 영)이다. 따라서 다음이 성립한다.
$\quad$ 첫 번째는 미니맥스 부등식(minimax inequality)으로, 이는 두 개의 독립 변수를 가진 임의의 함수 $\varphi(\boldsymbol{x}, \boldsymbol{y})$ 에 대해 맥시민(maximin)이 미니맥스(minimax)보다 작거나 같다는 것을 말한다. 즉,
이 부등식은 다음의 부등식을 고려함으로써 증명될 수 있다.
(7.24)의 좌변에 대해 $\boldsymbol{y}$ 에 대한 최댓값을 취해도, 해당 부등식이 모든 $\boldsymbol{y}$ 에 대해 참이므로 부등호의 방향이 유지됨에 유의하라. 유사하게, (7.24)의 우변에 대해 $\boldsymbol{x}$ 에 대한 최솟값을 취하여 (7.23)을 얻을 수 있다.
$\quad$ 두 번째 개념은 약한 쌍대성(weak duality)으로, 이는 (7.23)을 사용하여 원초 문제의 값(primal values)이 항상 쌍대 문제의 값(dual values)보다 크거나 같음을 보여준다. 이는 (7.27)에서 더 자세히 설명된다. $\lozenge$
$\quad$ (7.18)의 $J(\boldsymbol{x})$ 와 (7.20b)의 라그랑지안 사이의 차이점은 우리가 지시 함수(indicator function)를 선형 함수로 완화(relax)시켰다는 점을 상기하라. 따라서 $\boldsymbol{\lambda} \geqslant \boldsymbol{0}$ 일 때, 라그랑지안 $\mathfrak{L}(\boldsymbol{x}, \boldsymbol{\lambda})$ 은 $J(\boldsymbol{x})$ 의 하한(lower bound)이 된다. 그러므로 $\boldsymbol{\lambda}$ 에 대한 $\mathfrak{L}(\boldsymbol{x}, \boldsymbol{\lambda})$ 의 최댓값은 다음과 같다.
$\quad$ 원래의 문제는 $J(\boldsymbol{x})$ 를 최소화하는 것이었음을 상기하라.
미니맥스 부등식 (7.23)에 의해, 최솟값과 최댓값의 순서를 바꾸면 더 작은 값을 낳게 된다. 즉,
이것은 또한 약한 쌍대성(weak duality)으로 알려져 있다. 우변의 안쪽 부분이 쌍대 목적 함수 $\mathfrak{D}(\boldsymbol{\lambda})$ 이며 정의가 뒤따름에 유의하라.
$\quad$ 제약 조건을 가지는 원래의 최적화 문제와 대조적으로, $\min_{\boldsymbol{x} \in \mathbb{R}^d} \mathfrak{L}(\boldsymbol{x}, \boldsymbol{\lambda})$ 는 주어진 $\boldsymbol{\lambda}$ 값에 대한 제약 없는 최적화 문제(unconstrained optimization problem)이다. 만약 $\min_{\boldsymbol{x} \in \mathbb{R}^d} \mathfrak{L}(\boldsymbol{x}, \boldsymbol{\lambda})$ 를 푸는 것이 쉽다면, 전체 문제 또한 풀기 쉬워진다. 우리는 (7.20b)로부터 $\mathfrak{L}(\boldsymbol{x}, \boldsymbol{\lambda})$ 가 $\boldsymbol{\lambda}$ 에 대해 아핀(affine)이라는 것을 관찰함으로써 이를 확인할 수 있다. 따라서 $\min_{\boldsymbol{x} \in \mathbb{R}^d} \mathfrak{L}(\boldsymbol{x}, \boldsymbol{\lambda})$ 는 $\boldsymbol{\lambda}$ 에 대한 아핀 함수들의 점별 최솟값(pointwise minimum)이 되며, 결과적으로 $f(\cdot)$ 와 $g_i(\cdot)$ 가 비볼록(nonconvex)일지라도 $\mathfrak{D}(\boldsymbol{\lambda})$ 는 오목 함수(concave)가 된다. 외부의 문제인 $\boldsymbol{\lambda}$ 에 대한 최대화는 오목 함수의 최댓값을 구하는 것이므로 효율적으로 계산될 수 있다.
$\quad$ $f(\cdot)$ 와 $g_i(\cdot)$ 가 미분 가능하다고 가정하면, 우리는 라그랑지안을 $\boldsymbol{x}$ 에 대해 미분하고 그 미분값을 영(zero)으로 둔 뒤 최적값을 풀어서 라그랑주 쌍대 문제를 찾을 수 있다. 우리는 7.3.1절과 7.3.2절에서 $f(\cdot)$ 와 $g_i(\cdot)$ 가 볼록(convex)인 두 가지 구체적인 예시를 논의할 것이다.
주의 (등식 제약 조건). 다음의 추가적인 등식 제약 조건(equality constraints)을 가진 (7.17)을 고려하자.
우리는 등식 제약 조건을 두 개의 부등식 제약 조건으로 대체함으로써 등식 제약 조건을 모델링할 수 있다. 즉, 각각의 등식 제약 조건 $h_j(\boldsymbol{x}) = 0$ 에 대해, 이를 동등한 두 개의 제약 조건 $h_j(\boldsymbol{x}) \leqslant 0$ 및 $h_j(\boldsymbol{x}) \geqslant 0$ 으로 대체한다. 이렇게 하면 결과적으로 생성되는 라그랑주 승수들은 제약이 없어지게 됨(unconstrained)이 밝혀진다.
$\quad$ 따라서, 우리는 (7.28)에서 부등식 제약 조건에 대응하는 라그랑주 승수들은 음수가 아니도록(non-negative) 제약하고, 등식 제약 조건에 대응하는 라그랑주 승수들은 제약이 없는 상태(unconstrained)로 남겨둔다. $\lozenge$
$\to$ 만약 $g(\boldsymbol{x}) > 0$ 일 때 $\lambda g(\boldsymbol{x})$ 를 발산 시키기 위해 $\lambda$ 를 양수로 커지게 해야되며, 반대로 $g(\boldsymbol{x}) \leqslant 0$ 일 때 $\lambda g(\boldsymbol{x}) \leqslant 0$ 이 되어 원래 함수보다 작거나 같다는 하한을 형성하려면 부호가 바뀌지 않도록 $\lambda$ 는 0 이상의 값을 가져야 한다. 따라서 부등식의 라그랑주 승수는 음수가 될 수 없다.
반면 등식 제약 $h(\boldsymbol{x}) = 0$ 은 두 개의 부등식 $h(\boldsymbol{x}) \leqslant 0$ , $h(\boldsymbol{x}) \geqslant 0 \implies -h(\boldsymbol{x}) \leqslant 0$ 이 동시에 성립하는 것과 같다. 이 두 개의 부등식 제약 조건에 각각 0 이상인 라그랑주 승수 $\lambda_1 \geqslant 0$ 과 $\lambda_2 \geqslant 0$ 을 부여하여 라그랑지안의 패널티 항으로 더하면 다음과 같다.
이때 두 양수 $\lambda_1, \lambda_2$ 의 결과는 어떠한 실수이든 가능하다. 따라서 이를 새 변수 $\nu$ 로 치환( $\nu = \lambda_1 - \lambda_2$ )하면, $\nu$ 는 양수, 음수, 0을 모두 포함한다( $\nu \in \mathbb{R}$ , =제약이 없다).